package com.interview.javabase.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @description:
 * @author: zhangshuguang@vichain.com
 * @date: 2019/07/24 11:19
 */
public class QuickSort {

    public static void search(Integer[] arr, Integer low, Integer high) {

        if (low > high) {
            return;
        }
        int temp = arr[low];
        int i = low;
        int j = high;

        while (i < j) {
            while (temp <= arr[j] && i < j) {
                j--;
            }
            arr[i] = arr[j];
            while (temp >= arr[i] && i < j) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;
        search(arr, low, i - 1);
        search(arr, i + 1, high);
    }

    public static void main(String[] args) {

        int[] arr = {9, 3, 12, 1, 253, 634, 2, 12, 313, 531, 64, 52, 3, 23, 523, 15, 13};

        quickSort(arr, 0, arr.length - 1);

        for (Integer integer : arr) {
            System.out.print(integer + " ");
        }
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low > high) {
            return;
        }

        int i = low;
        int j = high;
        int temp = arr[i];
        while (i < j) {
            while (i < j && temp <= arr[j]) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && temp >= arr[i]) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = temp;

        // 左递归
        quickSort(arr, low, i - 1);

        // 右递归
        quickSort(arr, i + 1, high);
    }
}
